package leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-25 13:04
 **/
public class LeetCode1609 {

    public boolean isEvenOddTree(TreeNode root) {

        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        //flag = false:表示奇数行, = true:表示偶数行
        boolean flag = false;
        while (!deque.isEmpty()) {
            int size = deque.size();
            int pre = flag ? Integer.MAX_VALUE : Integer.MIN_VALUE;

            for (int i = 0; i < size; ++i) {
                TreeNode temp = deque.poll();

                if (temp.left != null) {
                    deque.offer(temp.left);
                }

                if (temp.right != null) {
                    deque.offer(temp.right);
                }

                if (flag) {
                    if (temp.val % 2 != 0 || temp.val >= pre) {
                        return false;
                    }
                    pre = temp.val;
                } else {
                    if (temp.val % 2 != 1 || temp.val <= pre) {
                        return false;
                    }
                    pre = temp.val;
                }
            }

            //flag取反,下一行奇偶交替
            flag = !flag;
        }

        return true;
    }

}
